/*
 * bst/base.hh - Base types declarations.
 * Copyright (C) 2008  Mikhail Vorozhtsov
 * See the LICENSE section of the README file for details.
 */

/* $Id$ */

#ifndef HEADER_LIBBST_MJ_BASE_HH
#define HEADER_LIBBST_MJ_BASE_HH

START_NAMESPACE (LIBBST_NS)

template <typename A, typename B>
class compare
{
public:
  INLINE
  static bool
  eq_p (const A &a, const B &b)
  {
    return a == b;
  }

  INLINE
  static bool
  less_p (const A &a, const B &b)
  {
    return a < b;
  }
};

template <typename T>
class compare_ptr
{
public:
  INLINE
  static bool
  eq_p (const T &t1, const T &t2)
  {
    return &t1 == &t2;
  }

  INLINE
  static bool
  less_p (const T &t1, const T &t2)
  {
    return &t1 < &t2;
  }
};

template <typename T, typename CMP>
class compare_with_ptr
{
public:
  INLINE
  static bool
  eq_p (const T &t, const T * const &p)
  {
    return &t == p;
  }

  INLINE
  static bool
  less_p (const T &t, const T * const &p)
  {
    return CMP::less_p (t, *p);
  }
};

template <typename STACK, typename NODE, int FAKE = 0>
class wrap_stack_t;

struct full_stack_t
{
};

template <typename NODE>
class wrap_stack_t<full_stack_t, NODE, 0>
{
public:
  wrap_stack_t (full_stack_t &stack UNUSED)
  {
  }

public:
  INLINE
  void
  push (NODE *x UNUSED)
  {
  }

  INLINE
  void
  pop ()
  {
  }

  template <typename TREE>
  INLINE
  NODE *
  pop (TREE *tree, NODE *x)
  {
    return x->get_parent (tree, (NODE *) tree->get_root ());
  }

  INLINE
  void
  mark ()
  {
  }

  INLINE
  NODE *
  replace_mark (NODE *x UNUSED)
  {
    return NULL;
  }

  INLINE
  void
  empty ()
  {
  }
};

template <typename STACK, typename NODE>
class wrap_stack_t<STACK, NODE, 0>
{
private:
  STACK *stack;
  u64_t _size;
  u64_t _overhead;
  u64_t _total_overhead;

public:
  wrap_stack_t (STACK &stack)
  {
    this->stack = &stack;
    _size = 0;
    _overhead = 0;
    _total_overhead = 0;
  }

public:
  INLINE
  void
  push (NODE *x)
  {
    if (_overhead > 0 || !stack->push (x))
      {
        ++_overhead;
        ++_total_overhead;
      }
    else
      ++_size;
  }

  INLINE
  void
  pop ()
  {
    if (_overhead > 0)
      --_overhead;
    else
      {
        --_size;
        stack->pop ();
      }
  }

  template <typename TREE>
  INLINE
  NODE *
  pop (TREE *tree, NODE *x)
  {
    if (_overhead > 0)
      {
        --_overhead;
        if (_size > 0)
          return x->get_parent (tree, (NODE *) stack->top ());
        else
          return x->get_parent (tree, (NODE *) tree->get_root ());
      }
    else
      {
        --_size;
        return (NODE *) stack->pop ();
      }
  }

  INLINE
  void
  mark ()
  {
    stack->mark ();
  }

  INLINE
  NODE *
  replace_mark (NODE *x)
  {
    return (NODE *) stack->replace_mark (x);
  }

  void
  empty ()
  {
    _overhead = 0;

    for (; _size > 0; --_size)
      stack->pop ();

    stack->stats (_total_overhead);
    _total_overhead = 0;
  }
};

struct basic_node_t
{
protected:
  static const unsigned int BASE_SHIFT = 3;
  static const u64_t BASE_MASK = ~U64 (7);

public:
  union ptr_t
  {
    struct
      {
        u64_t bit0 : 1;
        u64_t bit1 : 1;
        u64_t bit2 : 1;
        u64_t base : 61;
      };
    struct
      {
        u64_t : 1;
        u64_t bits12 : 2;
        u64_t : 61;
      };
    u64_t raw;
  };

protected:
  ptr_t left;
  ptr_t right;

public:
  INLINE
  struct basic_node_t *
  get_left () const
  {
    return (struct basic_node_t *) left.raw;
  }

  INLINE
  void
  set_left (struct basic_node_t *x)
  {
    left.raw = (u64_t) x;
  }

  INLINE
  struct basic_node_t *
  get_right () const
  {
    return (struct basic_node_t *) right.raw;
  }

  INLINE
  void
  set_right (struct basic_node_t *x)
  {
    right.raw = (u64_t) x;
  }
};

template <typename T, class P, u64_t OFFSET, typename CMP>
class base_node_t : public P
{
public:
  typedef T container_t;
  typedef CMP cmp_t;

private:
  typedef base_node_t node_t;

public:
  INLINE
  T *
  to_container ()
  {
    return (T *) ((void *) this - OFFSET);
  }

  INLINE
  const container_t *
  to_container () const
  {
    return (const T *) ((const void *) this - OFFSET);
  }

  static
  node_t *
  from_container (T *t)
  {
    return (node_t *) ((void *) t + OFFSET);
  }

  INLINE
  static
  const node_t *
  from_container (const T *t)
  {
    return (const node_t *) ((const void *) t + OFFSET);
  }

public:
  template <typename NODE, typename STACK>
  NODE *
  get_min (NODE *&parent, STACK &stack) const
  {
    NODE *n = (NODE *) this;

    for (NODE *left = (NODE *) n->get_left (); left;
         n = left, left = (NODE *) n->get_left ())
      {
        parent = n;
        stack.push (parent);
      }

    return n;
  }

  template <typename NODE>
  NODE *
  get_min (NODE *&parent) const
  {
    full_stack_t _stack;
    wrap_stack_t<full_stack_t, NODE> stack (_stack);
    return get_min (parent, stack);
  }

  template <typename NODE, typename STACK>
  NODE *
  get_min_and_replace (NODE *&parent, STACK &stack) const
  {
    stack.mark ();
    stack.push (parent);
    NODE *result = get_min (parent, stack);
    stack.replace_mark (result);
    return result;
  }

  template <typename NODE, typename STACK>
  NODE *
  get_max (NODE *&parent, STACK &stack) const
  {
    NODE *n = (NODE *) this;

    for (NODE *right = (NODE *) n->get_right (); right;
         n = right, right = (NODE *) n->get_right ())
      {
        parent = n;
        stack.push (parent);
      }

    return n;
  }

  template <typename NODE>
  NODE *
  get_max (NODE *&parent) const
  {
    full_stack_t _stack;
    wrap_stack_t<full_stack_t, NODE> stack (_stack);
    return get_max (parent, stack);
  }

  template <typename NODE, typename STACK>
  NODE *
  get_max_and_replace (NODE *&parent, STACK &stack) const
  {
    stack.mark ();
    stack.push (parent);
    NODE *result = get_max (parent, stack);
    stack.replace_mark (result);
    return result;
  }

  template <typename NODE, typename TREE, typename STACK>
  NODE *
  get_prev (TREE *tree, STACK &stack) const
  {
    NODE *child = ((NODE *) this)->get_left (); 
    NODE *parent;

    if (child)
      return child->get_max (parent, stack);

    child = (NODE *) this;

    for (parent = stack.pop (tree, child); parent != NULL;
         child = parent, parent = stack.pop (tree, child))
      {
        if (parent->get_right () == child)
          return parent;
      }

    return NULL;
  }

  template <typename NODE, typename TREE, typename STACK>
  NODE *
  get_next (TREE *tree, STACK &stack) const
  {
    NODE *child = ((NODE *) this)->get_right (); 
    NODE *parent;

    if (child)
      return child->get_min (parent, stack);

    child = (NODE *) this;

    for (parent = stack.pop (tree, child); parent != NULL;
         child = parent, parent = stack.pop (tree, child))
      {
        if (parent->get_left () == child)
          return parent;
      }

    return NULL;
  }
};

#define __LIBBST_MJ_NODE_WRAPPERS \
  INLINE \
  static \
  node_t * \
  from_container (typename parent_t::container_t *x) \
  { \
    return (node_t *) parent_t::from_container (x); \
  } \
  \
  INLINE \
  static \
  const node_t * \
  from_container (const typename parent_t::container_t *x) \
  { \
    return (const node_t *) parent_t::from_container (x); \
  } \
  \
  INLINE \
  node_t * \
  get_left () \
  { \
    return (node_t *) parent_t::get_left (); \
  } \
  \
  INLINE \
  node_t * \
  get_right () \
  { \
    return (node_t *) parent_t::get_right (); \
  } \
  \
  template <typename TREE, typename STACK> \
  INLINE \
  node_t * \
  get_prev (TREE *tree, STACK &stack) const \
  { \
    return parent_t::template get_prev<node_t, TREE, STACK> (tree, stack); \
  } \
  \
  template <typename TREE, typename STACK> \
  INLINE \
  node_t * \
  get_next (TREE *tree, STACK &stack) const \
  { \
    return parent_t::template get_next<node_t, TREE, STACK> (tree, stack); \
  }

#define __LIBBST_MJ_NODE_ORD_PREV \
  template <typename TREE> \
  INLINE \
  node_t * \
  get_prev (TREE *tree) const \
  { \
    full_stack_t _stack; \
    wrap_stack_t<full_stack_t, node_t> stack (_stack); \
    return (node_t *) get_prev (tree, stack); \
  }

#define __LIBBST_MJ_NODE_ORD_NEXT \
  template <typename TREE> \
  INLINE \
  node_t * \
  get_next (TREE *tree) const \
  { \
    full_stack_t _stack; \
    wrap_stack_t<full_stack_t, node_t> stack (_stack); \
    return (node_t *) get_next (tree, stack); \
  }

struct basic_tree_t
{
protected:
  void *root;

public:
  INLINE
  void *
  get_root () const
  {
    return root; 
  }

  INLINE
  void
  set_root (void *root)
  {
    this->root = root;
  }
};

struct basic_min_tree_t : public basic_tree_t
{
protected:
  void *min;

protected:
  INLINE
  void *
  get_min () const
  {
    return min;
  }

  INLINE
  void
  set_min (void *x)
  {
    min = x;
  }
};

struct basic_minmax_tree_t : public basic_min_tree_t
{
protected:
  void *max;

protected:
  INLINE
  void *
  get_max () const
  {
    return max;
  }

  INLINE
  void
  set_max (void *x)
  {
    max = x;
  }
};

template <class P, typename NODE, typename GLUE>
class pre_wrap_tree_t;

template <class NODE, typename TREE, typename GLUE>
class fwd_base_tree_t;

class glue_t;

template <class P, typename NODE>
class pre_wrap_tree_t<P, NODE, glue_t> : public P
{
public:
  INLINE
  NODE *
  get_root () const
  {
    return (NODE *) P::get_root ();
  };

  INLINE
  void
  set_root (NODE *x)
  {
    P::set_root (x);
  }
};

template <class NODE, class TREE>
class fwd_base_tree_t<NODE, TREE, glue_t> : public TREE
{
public:
  typedef NODE node_t;

protected:
  fwd_base_tree_t ()
  {
    this->set_root (NULL);
  }

protected:
  template <typename KEY, typename CMP, typename STACK>
  typename NODE::container_t *
  full_lookup_key (const KEY &key, NODE *&parent, bool &left_p,
                   NODE *&prev_or_next, STACK &stack)
    const
  {
    NODE *root = (NODE *) this->get_root ();
    NODE *n = root;

    for (parent = NULL, left_p = false, prev_or_next = NULL; n;)
      {
        typename NODE::container_t *x = n->to_container ();

        if (CMP::eq_p (*x, key))
          return x;

        if (CMP::less_p (*x, key))
          {
            if (left_p)
              prev_or_next = parent;

            parent = n;
            stack.push (parent);
            n = (node_t *) n->get_right ();
            left_p = false;
          }
        else
          {
            if (!left_p)
              prev_or_next = parent;

            parent = n;
            stack.push (parent);
            n = (node_t *) n->get_left ();
            left_p = true;
          }
      }

    return NULL;
  }

  template <typename KEY, typename STACK>
  INLINE
  typename NODE::container_t *
  full_lookup_key (const KEY &key, NODE *&parent, bool &left_p,
                   NODE *&prev_or_next, STACK &stack)
    const
  {
    return full_lookup_key <KEY, compare<typename NODE::container_t, KEY>,
                            STACK> (key, parent, left_p, prev_or_next, stack);
  }

  template <typename STACK>
  INLINE
  bool
  full_lookup (const typename NODE::container_t *x, NODE *&parent,
               bool &left_p, NODE *&prev_or_next, STACK &stack) const
  {
    return full_lookup_key <typename NODE::container_t const *,
                            compare_with_ptr<typename NODE::container_t,
                                             typename NODE::cmp_t>, STACK>
             (x, parent, left_p, prev_or_next, stack) != NULL;
  }

  template <typename KEY, typename CMP>
  INLINE
  typename NODE::container_t *
  full_lookup_key (const KEY &key, NODE *&parent, bool &left_p,
                   NODE *&prev_or_next) const
  {
    full_stack_t _stack;
    wrap_stack_t<full_stack_t, NODE> stack (_stack);
    return full_lookup_key<KEY, CMP, typeof (stack)>
             (key, parent, left_p, prev_or_next, stack);
  }

  template <typename KEY>
  INLINE
  typename NODE::container_t *
  full_lookup_key (const KEY &key, NODE *&parent, bool &left_p,
                   NODE *&prev_or_next) const
  {
    return full_lookup_key <KEY, compare<typename NODE::container_t, KEY> >
             (key, parent, left_p, prev_or_next);
  }

  INLINE
  bool
  full_lookup (const typename NODE::container_t *x, NODE *&parent,
               bool &left_p, NODE *&prev_or_next) const
  {
    return full_lookup_key <typename NODE::container_t const *,
                            compare_with_ptr<typename NODE::container_t,
                                             typename NODE::cmp_t> >
             (x, parent, left_p, prev_or_next) != NULL;
  }

protected:
  INLINE
  void
  before_insert (NODE *x UNUSED, NODE *parent UNUSED, bool left_p UNUSED)
  {
  }

  INLINE
  void
  after_remove (NODE *x UNUSED, NODE *parent UNUSED, NODE *pred UNUSED,
                bool has_right_p UNUSED, NODE *succ UNUSED)
  {
  }

public:
  template <typename STACK>
  typename NODE::container_t *
  get_min (STACK &stack) const
  {
    NODE *root = (NODE *) this->get_root ();

    if (root == NULL)
      return NULL;

    NODE *parent;
    return root->get_min (parent, stack)->to_container ();
  }

  INLINE
  typename NODE::container_t *
  get_min () const
  {
    full_stack_t _stack;
    wrap_stack_t<full_stack_t, NODE> stack (_stack);
    return get_min (stack);
  }

  template <typename STACK>
  typename NODE::container_t *
  get_max (STACK &stack) const
  {
    NODE *root = (NODE *) this->get_root ();

    if (root == NULL)
      return NULL;

    NODE *parent;
    return root->get_max (parent, stack)->to_container ();
  }

  INLINE
  typename NODE::container_t *
  get_max () const
  {
    full_stack_t _stack;
    wrap_stack_t<full_stack_t, NODE> stack (_stack);
    return get_max (stack);
  }

public:
  void
  replace (typename NODE::container_t *x, typename NODE::container_t *with)
  {
    NODE *node = NODE::from_container (x);
    NODE *with_node = NODE::from_container (with);
    node->replace (this, with_node);
  }

public:
  INLINE
  bool
  __test_unit__contains_p (const typename NODE::container_t *x) const
  {
    NODE *parent, *prev_or_next;
    bool left_p;
    return full_lookup (x, parent, left_p, prev_or_next);
  }
};

class min_glue_t;

template <class P, typename NODE>
class pre_wrap_tree_t<P, NODE, min_glue_t>: public pre_wrap_tree_t<P, NODE, glue_t>
{
protected:
  INLINE
  NODE *
  get_min () const
  {
    return (NODE *) P::get_min ();
  }

  INLINE
  void
  set_min (NODE *x)
  {
    P::set_min (x);
  }
};

template <class NODE, class TREE>
class fwd_base_tree_t<NODE, TREE, min_glue_t>
  : public fwd_base_tree_t<NODE, TREE, glue_t>
{
protected:
  INLINE
  fwd_base_tree_t ()
  {
    this->set_min (NULL);
  }

protected:
  INLINE
  void
  before_insert (NODE *x, NODE *parent, bool left_p)
  {
    if (parent == TREE::get_min () && (left_p || parent == NULL))
      this->set_min (x);
  }

  void
  after_remove (NODE *x, NODE *parent, NODE *pred, bool has_right_p, NODE *succ)
  {
    if (x != TREE::get_min ())
      return;

    if (has_right_p)
      {
        if (succ == NULL)
          succ = (NODE *) pred->get_next (this);
        this->set_min (succ);
      }
    else
      this->set_min (parent);
  }

public:
  INLINE
  typename NODE::container_t *
  get_min () const
  {
    return TREE::get_min ()->to_container ();
  }

public:
  void
  replace (typename NODE::container_t *x, typename NODE::container_t *with)
  {
    NODE *min = TREE::get_min ();
    NODE *node = NODE::from_container (x);
    NODE *with_node = NODE::from_container (with);

    fwd_base_tree_t<NODE, TREE, glue_t>::replace (x, with);

    if (min == node)
      this->set_min (with_node);
  }
};

class minmax_glue_t;

template <class P, typename NODE>
class pre_wrap_tree_t<P, NODE, minmax_glue_t>
  : public pre_wrap_tree_t<P, NODE, min_glue_t>
{
protected:
  INLINE
  NODE *
  get_max () const
  {
    return (NODE *) P::get_max ();
  }

  INLINE
  void
  set_max (NODE *x)
  {
    P::set_max (x);
  }
};

template <class NODE, class TREE>
class fwd_base_tree_t<NODE, TREE, minmax_glue_t>
  : public fwd_base_tree_t<NODE, TREE, min_glue_t>
{
protected:
  fwd_base_tree_t ()
  {
    this->set_max (NULL);
  }

protected:
  INLINE
  void
  before_insert (NODE *x, NODE *parent, bool left_p)
  {
    if (parent == TREE::get_min ())
      {
        if (left_p || parent == NULL)
          this->set_min (x);
      }

    if (parent == TREE::get_max ())
      {
        if (!left_p || parent == NULL)
          this->set_max (x);
      }
  }

  void
  after_remove (NODE *x, NODE *parent, NODE *pred, bool has_right_p, NODE *succ)
  {
    if (x == TREE::get_min ())
      {
        if (has_right_p)
          {
            if (succ == NULL)
              succ = (NODE *) pred->get_next (this);
            this->set_min (succ);
          }
        else
          this->set_min (parent);
      }

    if (x == TREE::get_max ())
      {
        if (pred)
          this->set_max (pred);
        else
          this->set_max (parent);
      }
  }

public:
  INLINE
  typename NODE::container_t *
  get_max () const
  {
    return TREE::get_max ()->to_container ();
  }

public:
  void
  replace (typename NODE::container_t *x, typename NODE::container_t *with)
  {
    NODE *max = TREE::get_max ();
    NODE *node = NODE::from_container (x);
    NODE *with_node = NODE::from_container (with);

    fwd_base_tree_t<NODE, TREE, min_glue_t>::replace (x, with);

    if (max == node)
      this->set_max (with_node);
  }
};

template <class NODE, class TREE, typename GLUE>
class base_tree_t
  : public fwd_base_tree_t<NODE, pre_wrap_tree_t<TREE, NODE, GLUE>, GLUE>
{
};

template <class P>
class wrap_tree_t : public P
{
public:
  INLINE
  typename P::node_t::container_t *
  get_prev (typename P::node_t::container_t *x) const
  {
    typename P::node_t *node = P::node_t::from_container (x)->get_prev (this);
    return node ? node->to_container () : NULL;
  }

  INLINE
  const typename P::node_t::container_t *
  get_prev (const typename P::node_t::container_t *x) const
  {
    const typename P::node_t *node
      = P::node_t::from_container (x)->get_prev (this);
    return node ? node->to_container () : NULL;
  }

  INLINE
  typename P::node_t::container_t *
  get_next (typename P::node_t::container_t *x) const
  {
    typename P::node_t *node = P::node_t::from_container (x)->get_next (this);
    return node ? node->to_container () : NULL;
  }

  INLINE
  const typename P::node_t::container_t *
  get_next (const typename P::node_t::container_t *x) const
  {
    const typename P::node_t *node
      = P::node_t::from_container (x)->get_next (this);
    return node ? node->to_container () : NULL;
  }

public:
  template <typename KEY, typename CMP, typename STACK>
  INLINE
  typename P::node_t::container_t *
  lookup_key (const KEY &key, STACK &_stack) const
  {
    wrap_stack_t<STACK, typename P::node_t> stack (_stack);
    typename P::node_t::container_t *result
      = P::template lookup_key<KEY, CMP, typeof (stack)> (key, stack);
    stack.empty ();
    return result;
  }

  template <typename KEY, typename CMP>
  INLINE
  typename P::node_t::container_t *
  lookup_key (const KEY &key) const
  {
    full_stack_t stack;
    return lookup_key<KEY, CMP, full_stack_t> (key, stack);
  }

  template <typename KEY, typename STACK>
  INLINE
  typename P::node_t::container_t *
  lookup_key (const KEY &key, STACK &stack) const
  {
    return lookup_key<KEY, compare<typename P::node_t::container_t, KEY>,
                      STACK> (key, stack);
  }

  template <typename KEY>
  INLINE
  typename P::node_t::container_t *
  lookup_key (const KEY &key) const
  {
    return lookup_key<KEY, compare<typename P::node_t::container_t, KEY> >
             (key);
  }

  template <typename STACK>
  INLINE
  bool
  lookup (const typename P::node_t::container_t *x, STACK &stack) const
  {
    return lookup_key<typename P::node_t::container_t const *,
                      compare_with_ptr<typename P::node_t::container_t,
                                       typename P::node_t::cmp_t>,
                      STACK> (x, stack) != NULL;
  }

  INLINE
  bool
  lookup (const typename P::node_t::container_t *x) const
  {
    full_stack_t stack;
    return lookup (x, stack);
  }

  template <typename STACK>
  INLINE
  bool
  insert (typename P::node_t::container_t *x, STACK &_stack)
  {
    wrap_stack_t<STACK, typename P::node_t> stack (_stack);
    bool result = P::insert (x, stack);
    stack.empty ();
    return result;
  }

  INLINE
  bool
  insert (typename P::node_t::container_t *x)
  {
    full_stack_t stack;
    return insert (x, stack);
  }

  template <typename KEY, typename CMP, typename STACK>
  INLINE
  typename P::node_t::container_t *
  remove_key (const KEY &key, STACK &_stack)
  {
    wrap_stack_t<STACK, typename P::node_t> stack (_stack);
    typename P::node_t::container_t *result
      = P::template remove_key<KEY, CMP, typeof (stack)> (key, stack);
    stack.empty ();
    return result;
  }

  template <typename KEY, typename STACK>
  INLINE
  typename P::node_t::container_t *
  remove_key (const KEY &key, STACK &stack)
  {
    return remove_key<KEY, compare<typename P::node_t::container_t, KEY>,
                     STACK> (key, stack);
  }

  template <typename STACK>
  bool
  remove (typename P::node_t::container_t *x, STACK &stack)
  {
    return remove_key<typename P::node_t::container_t const *,
                      compare_with_ptr<typename P::node_t::container_t,
                                       typename P::node_t::cmp_t>,
                      STACK> (x, stack) != NULL;
  }

  template <typename KEY, typename CMP>
  INLINE
  typename P::node_t::container_t *
  remove_key (const KEY &key)
  {
    full_stack_t stack;
    return remove_key<KEY, CMP, full_stack_t> (key, stack);
  }

  template <typename KEY>
  INLINE
  typename P::node_t::container_t *
  remove_key (const KEY &key)
  {
    return
      remove_key<KEY, compare<typename P::node_t::container_t, KEY> > (key);
  }

  INLINE
  bool
  remove (typename P::node_t::container_t *x)
  {
    full_stack_t stack;
    return remove (x, stack);
  }
};

template <class P>
class ord_lookup_tree_t : public P
{
public:
  template <typename KEY, typename CMP, typename STACK>
  INLINE
  typename P::node_t::container_t *
  lookup_key (const KEY &key, STACK &stack) const
  {
    typename P::node_t *parent, *prev_or_next;
    bool left_p;
    return P::template full_lookup_key<KEY, CMP, STACK>
                         (key, parent, left_p, prev_or_next, stack);
  }
};

END_NAMESPACE

#endif /* HEADER_LIBBST_MJ_BASE_HH */

